/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 17655
 * Date: 2025-02-18
 * Time: 11:46
 */
public class test3 {
    /**
     * LeetCode 5  最长回文子串
     */

    /**
     * 时间复杂度：O(N)
     */

    // 中心扩展算法
    public String longestPalindrome(String s) {
        int begin = 0;
        int n = s.length();
        int ret = 0;
        for(int i=0;i<n;i++){
            // 奇数
            int left = i;
            int right = i;
            while(left>=0 && right<n && s.charAt(left)==s.charAt(right)){
                left--;
                right++;

            }
            if(right-left-1>ret){
                begin = left+1;
                ret = right-left-1;
            }
            // 偶数
            left = i;
            right = i+1;
            while(left>=0 && right<n && s.charAt(left)==s.charAt(right)){
                left--;
                right++;

            }
            if(right-left-1>ret){
                begin = left+1;
                ret = right-left-1;
            }
        }
        return s.substring(begin,begin+ret);
    }
}
